home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / prog / dict / d_array_test.c next >
C/C++ Source or Header  |  1994-08-05  |  2KB  |  76 lines
  1. #include <LEDA/d_array.h>
  2. #include <LEDA/list.h>
  3.  
  4. #include <LEDA/impl/avl_tree.h>
  5. #include <LEDA/impl/rb_tree.h>
  6. #include <LEDA/impl/skiplist.h>
  7. #include <LEDA/impl/ch_hash.h>
  8.  
  9.  
  10. #if !defined(__TEMPLATE_ARGS_AS_BASE__)
  11. declare3(_d_array,int,int,avl_tree)
  12. declare3(_d_array,int,int,rb_tree)
  13. declare3(_d_array,int,int,skiplist)
  14. declare3(_d_array,int,int,ch_hash)
  15. #endif
  16.  
  17. void d_array_test(d_array<int,int>& count, list<int>& L, char* name)
  18. { 
  19.   int min;
  20.   int max;
  21.   int x;
  22.  
  23.   cout << string("%-10s",name);
  24.   cout.flush();
  25.  
  26.   float T = used_time();
  27.  
  28.  
  29.   forall(x,L) count[x]++;
  30.  
  31.   min = max = L.head();
  32.  
  33.   forall(x,L)
  34.   { if (count[x] > count[max]) max = x;
  35.     if (count[x] < count[min]) min = x;
  36.    }
  37.  
  38.   cout << "min: " << min << " appears " << count[min] << " times, ";
  39.   cout << "max: " << max << " appears " << count[max] << " times. ";
  40.   cout << string("   (%8.2f sec)",used_time(T));
  41.   newline;
  42. }
  43.  
  44.  
  45. main()
  46. {
  47.    d_array<int,int>           RS_ARRAY(0);
  48.  
  49. #if defined(__TEMPLATE_ARGS_AS_BASE__)
  50.   _d_array<int,int,avl_tree>  AVL_ARRAY(0);
  51.   _d_array<int,int,rb_tree>   RB_ARRAY(0);
  52.   _d_array<int,int,ch_hash>   CH_ARRAY(0);
  53.   _d_array<int,int,skiplist>  SK_ARRAY(0);
  54. #else
  55.   _d_array(int,int,avl_tree)  AVL_ARRAY(0);
  56.   _d_array(int,int,rb_tree)   RB_ARRAY(0);
  57.   _d_array(int,int,ch_hash)   CH_ARRAY(0);
  58.   _d_array(int,int,skiplist)  SK_ARRAY(0);
  59. #endif
  60.  
  61.   int N = read_int("# keys = ");
  62.  
  63.   list<int> L;
  64.  
  65.   while(N--) L.append(random(1,100));
  66.  
  67.   d_array_test(AVL_ARRAY,L,"avl_tree");
  68.   d_array_test(RS_ARRAY,L,"rs_tree");
  69.   d_array_test(RB_ARRAY,L,"rb_tree");
  70.   d_array_test(CH_ARRAY,L,"ch_hash");
  71.   d_array_test(SK_ARRAY,L,"skiplist");
  72.  
  73.   return 0;
  74. }
  75.  
  76.